543. 二叉树的直径
#leetcode#二叉树 2025-01-30

Problem: 543. 二叉树的直径

解析

递归

求节点的左右高度，即可求出经过该节点的最大路径长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//！ n,log(n)~n->时间复杂度每个节点只访问一次，空间复杂度看函数递归栈大小
class Solution {
 private:
  int res = 0;

 public:
  int diameterOfBinaryTree(TreeNode *root) {
    height(root);
    return res;
  }
  int height(TreeNode *node) {
    if (node == nullptr) {
      return 0;
    }
    int lHeight = height(node->left);
    int rHeight = height(node->right);
    res = max(res, lHeight + rHeight);
    return max(lHeight, rHeight) + 1;
  }
};